package graphic;

import java.util.*;

/**
 * @author pengfei.hpf
 * @date 2020/2/28
 * @verdion 1.0.0
 * 验证原始的序列 org 是否可以从序列集 seqs 中唯一地重建。序列 org 是 1 到 n 整数的排列，其中 1 ≤ n ≤ 104。重建是指在序列集 seqs 中构建最短的公共超序列。（即使得所有  seqs 中的序列都是该最短序列的子序列）。确定是否只可以从 seqs 重建唯一的序列，且该序列就是 org 。
 *
 * 示例 1：
 *
 * 输入：
 * org: [1,2,3], seqs: [[1,2],[1,3]]
 *
 * 输出：
 * false
 *
 * 解释：
 * [1,2,3] 不是可以被重建的唯一的序列，因为 [1,3,2] 也是一个合法的序列。
 *  
 *
 * 示例 2：
 *
 * 输入：
 * org: [1,2,3], seqs: [[1,2]]
 *
 * 输出：
 * false
 *
 * 解释：
 * 可以重建的序列只有 [1,2]。
 *  
 *
 * 示例 3：
 *
 * 输入：
 * org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]
 *
 * 输出：
 * true
 *
 * 解释：
 * 序列 [1,2], [1,3] 和 [2,3] 可以被唯一地重建为原始的序列 [1,2,3]。
 *  
 *
 * 示例 4：
 *
 * 输入：
 * org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]
 *
 * 输出：
 * true
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sequence-reconstruction
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SequenceReconstruction {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        //org == null?
        if(org == null || seqs == null || seqs.size() == 0){
            return false;
        }
        int size = org.length;
        Set<Integer> numSet = new HashSet<>();
        for (List<Integer> list : seqs) {
            for (Integer num: list) {
                if (num <= 0 || num > size) {
                    return false;
                }
                numSet.add(num);
            }
        }

        //情况1: 数目与原始不符
        if (numSet.size() < size) {
            return false;
        }
        int[] ingree = new int[size + 1];
        HashSet<Integer>[] graph = new HashSet[size + 1];
        for(List<Integer> list: seqs){
            for(int i = 1; i < list.size(); i ++){
                HashSet<Integer> nei = graph[list.get(i - 1)];
                if(nei == null){
                    nei = new HashSet<>();
                    graph[list.get(i - 1)] = nei;
                }
                nei.add(list.get(i));
            }
        }
        for(HashSet<Integer> set: graph){
            if(set != null){

                for(int i: set){
                    ingree[i] ++;
                }
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= size; i ++ ){
            if(ingree[i] == 0){
                queue.add(i);
            }
        }
        // 情况2: 入口有多个
        if(queue.size() != 1){
            return false;
        }
        int index = 0;
        while(!queue.isEmpty()){
            int num = queue.poll();
            if(num != org[index]){
                return false;
            }
            int next = 0;
            if(graph[num] != null){
                for(Integer nei: graph[num]){
                    ingree[nei] --;
                    if(ingree[nei] == 0){
                        queue.add(nei);
                        next ++;
                        if(next > 1){
                            //情况3: 下一轮入口有多个
                            return false;
                        }
                    }
                }
            }
            index ++;
        }
        //情况4: 有环
        return index == size;

    }
}
